package com.demo.study.algorithm.sorts;

import com.demo.study.utils.ArrayUtil;

import static com.demo.study.utils.ArrayUtil.printArray;
import static com.demo.study.utils.ArrayUtil.swap;

/**
 * 冒泡排序
 *
 * @author Baymax
 * @since 2024-08-07
 */
public class B01_BubbleSort {
    public static void main(String[] args) {
        int[] nums = ArrayUtil.intArray();
        sort(nums);
        ArrayUtil.printArray(nums);

        nums = ArrayUtil.intRandomArray();
        sortWithFlag(nums);
        ArrayUtil.printArray(nums);


        System.out.println("---------------以下为递归排序的用例--------------");
        int[] nums2 = ArrayUtil.intRandomArray();
        printArray(nums2);
        sortRecursionBase(nums2);
        printArray(nums2);

        // 改进版
        nums2 = ArrayUtil.intRandomArray();
        printArray(nums2);
        sortRecursionRevised(nums2);
        printArray(nums2);
    }

    /**
     * 冒泡排序：每一轮，都通过连续地比较与交换相邻元素实现排序，需要进行多次冒泡
     * 时间复杂度：O(n^2)
     */
    public static void sort(int[] nums) {
        // 外循环：未排序区间为 [0, i] --外层表示，每次需要冒泡的次数
        for (int i = nums.length - 1; i > 0; i--) {
            // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    // 交换 nums[j] 与 nums[j + 1]
                    swap(nums, i, i + 1);
                }
            }
        }
    }

    /**
     * 冒泡排序（标志优化）
     * 如果某一轮执行过程中，没有发生交换，则说明整个集合，已经排好序了，不需要再执行算法了
     * 时间复杂度：O(n^2)
     */
    public static void sortWithFlag(int[] nums) {
        // 外循环：未排序区间为 [0, i]
        for (int i = nums.length - 1; i > 0; i--) {
            boolean swapFlag = false; // 交换标志位
            // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    // 交换 nums[j] 与 nums[j + 1]
                    swap(nums, i, i + 1);
                    swapFlag = true; // 记录交换元素
                }
            }
            if (!swapFlag) {
                break; // 此轮“冒泡”未交换任何元素，直接跳出
            }
        }
    }

    /**
     * 基础版
     */
    public static void sortRecursionBase(int[] nums) {
        bubbleSortBase(nums, nums.length - 1);
    }

    private static void bubbleSortBase(int[] nums, int index) {
        // 就剩下一个元素时，直接返回
        if (index == 1) {
            return;
        }
        // 内循环：将未排序区间 [0, index] 中的最大元素交换至该区间的最右端
        for (int i = 0; i < index; i++) {
            if (nums[i] > nums[i + 1]) {
                // 交换 nums[i] 与 nums[i + 1]
                swap(nums, i, i + 1);
            }
        }
        // 递归调用
        bubbleSortBase(nums, index - 1);
    }

    /**
     * 修改版
     */
    public static void sortRecursionRevised(int[] nums) {
        bubbleSortRevised(nums, nums.length - 1);
    }

    // 修改版本，减少交换次数
    private static void bubbleSortRevised(int[] nums, int index) {
        // 就剩下一个元素时，直接返回
        if (index == 0) {
            return;
        }
        int x = 0; // 只要发生交换，x记录交换的起始位置i，x右侧就表表示已排序数据，左侧，表示未排序数据
        // 内循环：将未排序区间 [0, index] 中的最大元素交换至该区间的最右端
        for (int i = 0; i < index; i++) {
            if (nums[i] > nums[i + 1]) {
                // 交换 nums[i] 与 nums[i + 1]
                swap(nums, i, i + 1);
                x = i;
            }
        }
        // 递归调用
        bubbleSortRevised(nums, x);
    }
}
